# 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/
# 输入: root = [3,9,20,null,null,15,7]
#     3
#    / \
#   9  20
#     /  \
#    15   7
# 输出: true


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def process(node: TreeNode):
            if not node:
                return [0, True]
            l = process(node.left)
            r = process(node.right)
            h = max(l[0], r[0]) + 1
            isB = True if abs(l[0] - r[0]) < 2 else False
            return [h, isB and l[1] and r[1]]

        return process(root)[1]

    
